// https://leetcode.cn/problems/unique-substrings-in-wraparound-string/

/*
换种思路：
cbcbcdefabc

abcdfbcde

从头到尾遍历该字符串，取出每个字母开头的最长子串
a b c d ab bc cd abc bcd abcd 9 + 1 + 4 = 14
f 
e de cde bcde 

int findSubstringInWraproundString(string p) {
	vector<int> dp(26);
	int k = 0;
	for (int i = 0; i < p.length(); ++i) {
		if (i && (p[i] - p[i - 1] + 26) % 26 == 1) { // 字符之差为 1 或 -25
			++k;
		} else {
			k = 1;
		}
		dp[p[i] - 'a'] = max(dp[p[i] - 'a'], k);
	}
	return accumulate(dp.begin(), dp.end(), 0);
}


*/

#include <string>
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

class Solution {
public:
    int findSubstringInWraproundString(string p) {
		int len = p.size();
		int k = 0;
		vector<int> dp(26);
		for(int i = 0; i < len; i++){
			if(i && (p[i] - p[i-1] + 26 ) % 26 == 1){ // 这里的写法很巧妙
				k++;
			}else{
				k = 1;
			}
			dp[p[i] - 'a'] = max(dp[p[i] - 'a'], k); // 这里的写法也很巧妙
		}
		return accumulate(dp.begin(), dp.end(), 0);
    }
};

int main(){
	Solution so;
	// string p = "zab";
	// string p = "cac";
	string p = "abaab"; // cdecdc
	int sum = so.findSubstringInWraproundString(p);
	cout << sum << endl;
	return 0;
}